/*
Date:20210419 22:18pm
key:非常经典的考察了pair
    1.习惯认知map总和pair绑定，实际上pair是一种单独的数据类型<a,b>。
    2.pair能够绑定两个类，因此pair中还可以有pair，实现无限元组。
    3.本题的思路，首先将每个元素的sort值与元素绑定成pair(异位词就是字符排列顺序不同)，相同的sort值一定一样。
    4.不要放进map里，map会按key去重。
    5.放进vector中，再写一个排序函数。按照sort后的值排序，这样所有异位词就会相邻，然后直接遍历一次，相邻的元素不同则刷新临时vector。
    6.复杂度分析，每个串排序O(1*log1),然后排整个O(n*logn),最后遍历一次。

    在美版leetcode上看到大神的思路，用质数表示26个字母，把字符串的各个字母相乘，这样可保证字母异位词的乘积必定是相等的。其余步骤就是用map存储，和别人的一致了。（这个用质数表示真的很骚啊！！!）
*/

class Solution {
public:

static bool cmp_by_value(pair<string, string>& lhs, pair<string, string>& rhs) {
  return lhs.first < rhs.first;
}
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {

        vector<vector<string>>V;
        if(strs.size()==0){return V;}

        vector<pair<string,string>>v1;
        for(int i=0;i<strs.size();i++)
        {
            string a=strs[i];
            sort(a.begin(),a.end());
            v1.push_back(pair<string,string>(a,strs[i]));
        }
        sort(v1.begin(),v1.end(),cmp_by_value);
        vector<string>v;
        for(int i=0;i<v1.size();i++)
        {
            if(i==0)
            {
                v.push_back(v1[i].second);
            }
            else
            {
                if(v1[i].first==v1[i-1].first)
                {
                    v.push_back(v1[i].second);
                }
                else
                {
                    V.push_back(v);
                    v.clear();
                    v.push_back(v1[i].second);
                }
            }
        }
        if(!v.empty()){V.push_back(v);}
        
        return V;
    }
};